package leetcode_core.leetcode_1;

import java.util.LinkedList;

public class Codec2 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    private static final String SEP =",";
    private static final String NULL = "#";
    private StringBuilder sb;

    private void serialize(TreeNode root,StringBuilder sb){
        if(root == null){
            sb.append(NULL).append(SEP);
            return;
        }
        serialize(root.left,sb);
        serialize(root.right,sb);
        sb.append(root.val).append(SEP);
    }


    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        sb = new StringBuilder();
        serialize(root,sb);
        return sb.toString();
    }

    private TreeNode deserialize(LinkedList<String> lists){
        if(lists.isEmpty()){
            return null;
        }
        //寻找root节点,然后跟着走,后序遍历序列中,根节点位于列表的最末端
        String last = lists.removeLast();
        //然后根据左右根的序列顺序特点反推
        if(NULL.equals(last)){
            return null;
        }
        //然后先把根节点给造出来
        TreeNode node = new TreeNode(Integer.parseInt(last));
        //左右根
        node.right = deserialize(lists);
        node.left = deserialize(lists);
        return node;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nodes = data.split(",");
        LinkedList<String> list = new LinkedList<>();
        for (String node : nodes) {
            list.addLast(node);
        }
        TreeNode root = deserialize(list);
        return root;
    }



}
